#include "DynamicArray.h"
#include <cmath>
//using ElementType = int;

DynamicArray::DynamicArray():capacity(10),size(0)
{
    array = new ElementType[capacity];
}

DynamicArray::DynamicArray(const DynamicArray& a)
{
    size = a.size;
    capacity = a.capacity;
    array = new int[capacity];
    for(size_t i = 0;i < size;i++)
        array[i] = a.array[i];
}

DynamicArray& DynamicArray::operator=(const DynamicArray& a)
{
    delete []array;
    size = a.size;
    capacity = a.capacity;
    array = new int[capacity];
    for(size_t i = 0;i < size;i++)
        array[i] = a.array[i];
    return *this;
}

DynamicArray::~DynamicArray()
{
        delete []array;
}

void DynamicArray::InsertTail(const ElementType &element)// 不扩容：o(1) 扩容o(n)
{
    if(size == capacity)
    {
        ReSize(capacity*2);
    }
    array[size++] = element;
}

void DynamicArray::InsertHead(const ElementType &element)//o(n)
{
    if(size == capacity)
    {
        ReSize(capacity*2);
    }
    for(size_t i = size;i > 0;i--)
        array[i] = array[i - 1];
    array[0] = element;
    size++;
}

void DynamicArray::InserByIndex(const ElementType &element, size_t index)
{
    if(index > size)
    {
        std::cout<<"插入位置非法\n";
        return;
    }
    if(size == capacity)
    {
        ReSize(capacity*2);
    }
    for(size_t i = size;i > index;i--)
        array[i] = array[i - 1];
    array[index] = element;
    size++;
}

void DynamicArray::RemoveByIndex(size_t index)// o(n)
{
    if(index >= size)
    {
        std::cout<<"删除位置非法\n";
        return;
    }
    for(size_t i = index;i < size - 1;i++)
        array[i] = array[i + 1];
    size--;
}

void DynamicArray::RemoveByElement(const ElementType &element)// o(n^2)
{
    for(size_t i = 0;i < size;i++)
    {
        if(array[i] == element)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

ElementType *DynamicArray::FindByIndex(size_t index) // o(1)
{
    if(index >= size)
    {
        return nullptr;
    }
    return &array[index];
    
}

DynamicArray DynamicArray::FindByElement(const ElementType &element)// o(n)
{
    DynamicArray result;
    for(size_t i = 0;i < size;i++)
    {
        if(array[i] == element)
        {
            result.InsertTail(i);
        }
    }
    return result;
}

void DynamicArray::UpdateByIndex(size_t index, const ElementType &newvalue)// o(1)
{
    if(index >= size)
    {
        std::cout<<"删除位置非法\n";
        return;
    }
    array[index] = newvalue;
}

void DynamicArray::UpdateByElement(const ElementType &oldvalue, const ElementType &newvalue)
{
    int flag = 0;
    for(size_t i = 0;i < size;i++)
    {
        if(array[i] == oldvalue)
        {
            array[i] = newvalue;
            flag = 1;
        }
    }
    if(flag == 0)
        std::cout<<"没有此元素\n";
}

DynamicArray DynamicArray::Merge(const DynamicArray &a)//o(n) 稳定
{
    DynamicArray result;
    size_t first = 0;//当前
    size_t second = 0;//传入
    while(first < this->size && second < a.size)
    {
        if(array[first] < a.array[second])
            result.InsertTail(array[first++]);
        else
            result.InsertTail(a.array[second++]);
    }
    while(first < this->size)
        result.InsertTail(array[first++]);
    while(second < a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

ElementType &DynamicArray::operator[](int index)
{
    return array[index];
}

void DynamicArray::Sort()
{
    FastSort(0,size - 1,0,2 * log2(size));
}

void DynamicArray::Duplicate() //o(n)
{
    for(size_t i = 1;i < size;i++)
    {
        if(array[i] == array[i - 1])
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

DynamicArray DynamicArray::FdIntrSctn(const DynamicArray &a)// O(n)
{
    DynamicArray result;
    size_t first = 0;//当前
    size_t second = 0;//传入
    while(first < this->size && second < a.size)
    {
        if(array[first] == a.array[second])
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if(array[first] < a.array[second])
            first++;
        else if(array[first] > a.array[second])
            second++;    
    } 


    return result;
}

DynamicArray DynamicArray::FindUnionSet(const DynamicArray &a)
{
    DynamicArray result;
    size_t first = 0;//当前
    size_t second = 0;//传入
    while(first < this->size && second < a.size)
    {
        if(array[first] == a.array[second])
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if(array[first] < a.array[second])
            result.InsertTail(array[first++]);
        else if(array[first] > a.array[second])
            result.InsertTail(a.array[second++]);    
    }
    while(first < this->size)
        result.InsertTail(array[first++]);
    while(second < a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

DynamicArray DynamicArray::FindDifference(const DynamicArray &a)
{
     DynamicArray result;
    size_t first = 0;//当前
    size_t second = 0;//传入
    while(first < this->size && second < a.size)
    {
        if(array[first] == a.array[second])
        {
            first++;
            second++;
        }
        else if(array[first] < a.array[second])
            result.InsertTail(array[first++]);
        else if(array[first] > a.array[second])
            result.InsertTail(a.array[second++]);    
    }
    while(first < this->size)
        result.InsertTail(array[first++]);
    while(second < a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

bool DynamicArray::operator==(const DynamicArray &a)// o(n)
{
    if(size != a.size)
        return false;
    for(size_t i = 0;i < size;i++)
        if(array[i] != a.array[i])
            return false;
    return true;
}

size_t DynamicArray::BinarySearch(const ElementType &element)
{
    size_t left = 0;
    size_t right = size - 1;
    while(left <= right)
    {
        size_t mid = left + (right - left)/2;//
        if(array[mid] == element)
        {
            return mid;
        }
        else if(array[mid] > element)
        {
            if(mid == 0)
                return ULLONG_MAX;
            right = mid - 1;  
        }
        else if(array[mid] < element)
        {
            left = mid + 1;
        }
    }
    return ULLONG_MAX;
}

bool DynamicArray::Contains(const DynamicArray &a)
{
    size_t j = 0;
    for(size_t i = 0;i < size;i++)
    {
        if(array[i] == a.array[j])
            j++;
    }
    return j == a.size;
}

bool DynamicArray::ContnsContains(const DynamicArray &a)
{
    for(size_t i = 0;i <= size - a.size;i++ )
    {
        if(SubSquence(i,a.size) == a)
        {
            return true;
        }
    }
    return false;
}

DynamicArray DynamicArray::SubSquence(size_t index, size_t len)
{
    DynamicArray result;
    if(index + len > size)
        return result;
    for(size_t i = index;i < index + len;i++)
        result.InsertTail(array[i]);
    return result;
}

size_t DynamicArray::partition(size_t start, size_t end)
{
    size_t left = start;
    size_t right = end;
    ElementType temp = array[start];
    while(left < right)
    {
        while(array[right] > temp && left < right)
            right--;
        if(left < right)
            array[left++] = array[right];
        while(array[left] < temp && left < right)
            left++;
        if(left < right)
            array[right--] = array[left];
    }
    array[left] = temp;
    return left;
}

void DynamicArray::FastSort(size_t start, size_t end,size_t CurDepth, size_t MaxDepth)
{
    if(start >= end)
        return;

    //如果没有达到最大递归深度
    if(CurDepth < MaxDepth)
    {
        size_t par = partition(start,end);//对数列分组
        if(par != 0)
            FastSort(start ,par - 1,CurDepth + 1,MaxDepth);
        FastSort(par + 1 ,end,CurDepth + 1,MaxDepth);
    }
    //超过最大深度，改用插入排序
    else
    {
        InsertSort(start,end);
    }

}
void DynamicArray::InsertSort(size_t start, size_t end)
{
    for(size_t i = start  + 1;i <= end;i++)
    {
        size_t j = i;
        ElementType temp = array[i];
        for(;j > start;j--)
        {
            if(array[j - 1] > temp)
                array[j] = array[j - 1];
            else
                break;
        }
        array[j] = temp;
    }
}

void DynamicArray::ReSize(size_t capacity)
{
    this->capacity = capacity;
    size = size > capacity ? capacity :size  ;
    ElementType *newPtr = new ElementType[capacity];
    for(size_t i = 0;i < size;i++)
        newPtr[i] = array[i];
    delete []array;
    array = newPtr;
}

void DynamicArray::show()
{
    for(size_t i = 0;i < size;i++)
    {
        std::cout<<array[i]<<" ";
    }
    std::cout<<std::endl;
}
